翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク set cover problem ： ウィキペディア英語版 set cover problem The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. Given a set of elements $\backslash$ (called the universe) and a collection $S$ of $n$ sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of $S$ whose union equals the universe. For example, consider the universe $U\; =\; \backslash$ and the colletion of sets $S\; =\; \backslash ,\; \backslash ,\; \backslash \backslash \}$. Clearly the union of $S$ is $U$. However, we can cover all of the elements with the following, smaller number of sets: $\backslash \backslash \}$. More formally, given a universe $\backslash mathcal$ and a family $\backslash mathcal$ of subsets of $\backslash mathcal$, a ''cover'' is a subfamily $\backslash mathcal\backslash subseteq\backslash mathcal$ of sets whose union is $\backslash mathcal$. In the set covering decision problem, the input is a pair $(\backslash mathcal,\backslash mathcal)$ and an integer $k$; the question is whether there is a set covering of size $k$ or less. In the set covering optimization problem, the input is a pair $(\backslash mathcal,\backslash mathcal)$, and the task is to find a set covering that uses the fewest sets. The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard . If each set is assigned a cost, it becomes a ''weighted'' set cover problem. ==Integer linear program formulation== The minimum set cover problem can be formulated as the following integer linear program (ILP). x_S \geqslant 1 | for all $e\backslash in\; \backslash mathcal\; U$ | (cover every element of the universe) |- | | $x\_S\; \backslash in\; \backslash$ | for all $S\backslash in\; \backslash mathcal\; S$. | (every set is either in the set cover or not) |} This ILP belongs to the more general class of ILPs for covering problems. The integrality gap of this ILP is at most $\backslash scriptstyle\; \backslash log\; n$, so its relaxation gives a factor-$\backslash scriptstyle\; \backslash log\; n$ approximation algorithm for the minimum set cover problem (where $\backslash scriptstyle\; n$ is the size of the universe). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「set cover problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.